# 二进制问题(好题)


def count_num(n, k):
    if k == 0:
        return 0

    def combination(m, k):
        """计算组合数C(m, k)，从m中选取k个的不同的组合个数."""
        if k < 0 or k > m:
            return 0

        if k == 0 or k == m:
            return 1
        k = min(k, m - k)
        result = 1
        for i in range(1, k + 1):
            result = result * (m - k + i) // i
        return result

    bin_num = bin(n)[2:]
    bin_len = len(bin_num)
    zero_loc = []
    for i in range(len(bin_num)):
        if bin_num[i] == '0':
            zero_loc.append(i)
    count = 0
    # 找出所有比当前数大的同位数二进制的个数, 假定左边第一位为1, 判断剩余位为0的如果改为1并大于n的情况的个数
    for idx, loc in enumerate(zero_loc):
        one_cnt = loc - idx + 1  # 将首位和当前位都设为1后, 总计有几个1(idx表示当前位的前面有几个0)
        if k < one_cnt:
            break
        count += combination(bin_len - 1 - loc, k - one_cnt)

    return combination(bin_len, k) - count


def count_num_dp(n, k):
    """数位DP"""
    if k == 0:
        return 0
    s = bin(n)[2:]  # 二进制字符串，如5→'101'
    bits = list(map(int, s))
    m = len(bits)
    res = 0
    cnt_ones = 0  # 已选1的数量

    # 预计算组合数C(m, k)  可以参考杨辉三角
    C = [[0] * (k + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        C[i][0] = 1
        for j in range(1, min(i, k) + 1):
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1]

    for i in range(m):
        if bits[i] == 1:
            # 当前位选0时，剩余位数为m-i-1，需要选k - cnt_ones个1
            remaining = m - i - 1
            need = k - cnt_ones
            if 0 <= need <= remaining:
                res += C[remaining][need]
            # 当前位选1，更新已选1的数量
            cnt_ones += 1
            if cnt_ones > k:
                break
        # 当前位为0则必须选0，无需操作

    # 检查所有位都选中的情况（即n本身是否满足）
    if cnt_ones == k:
        res += 1

    return res


if __name__ == '__main__':
    print(count_num(7, 2))
    print(count_num(10000, 5))
    print(count_num(12345, 7))  # 2643
    print(count_num_dp(7, 2))
    print(count_num_dp(10000, 5))
    print(count_num_dp(12345, 7))  # 2643
